//给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。 
//
// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 
//
// 注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 
//
// 示例 1: 
//
// 输入: [2,4,1], k = 2
//输出: 2
//解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
// 
//
// 示例 2: 
//
// 输入: [3,2,6,5,0,3], k = 2
//输出: 7
//解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
//     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
// 
// Related Topics 动态规划
package leetcode.editor.cn;

import java.util.Objects;


//Java：Best Time to Buy and Sell Stock IV
public class P188BestTimeToBuyAndSellStockIv{
    public static void main(String[] args) {
        Solution solution = new P188BestTimeToBuyAndSellStockIv().new Solution();
        // TO TEST
        int[] prices = {3,2,6,5,0,3};
        int k = 2;
        int result = solution.maxProfit(k, prices);
        System.out.println(result);
    }
    

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxProfit(int k, int[] prices) {
        if(Objects.isNull(prices) || prices.length<1){
            return 0;
        }
        if(k<1){
            return 0;
        }
        int size = prices.length;
        if (k > size / 2) {
            int buy = 0, sale = Integer.MIN_VALUE;
            for (int i = 0; i < size; i++) {
                int temp = buy;
                buy = Math.max(buy, sale + prices[i]);
                sale = Math.max(sale, temp - prices[i]);
            }
            return buy;
        }
        /**
         * 1-代表持有股票
         * 0-代表未持有股票
         */
        int resMax = 0;
        int[][][] MP = new int[size][k+1][2];
        for(int i = 0;i < size; i++){
            for(int j = k; j >= 1; j--){
                if (i - 1 == -1) {
                    /* 处理 特殊 */
                    MP[i][k][0] = 0;
                    MP[i][k][1] = -prices[i];
                    continue;
                }
                //当前没有股票
                MP[i][j][0] = Math.max(MP[i-1][j][1] + prices[i], MP[i-1][j][0]);
                //当前有股票
                MP[i][j][1] = Math.max(MP[i-1][j-1][0] - prices[i], MP[i-1][j][1]);

                resMax = Math.max(resMax, MP[size-1][k][0]);
            }
        }
        return resMax;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
